5198. Возведение в степень

 

Вычислите значение выражения xn mod m.

 

Вход. Три натуральных числа x, n, m (1 ≤ x, n ≤ 109, 2 ≤ m ≤ 109).

 

Выход. Выведите одно число, равное xn mod m.

 

Пример входа

Пример выхода

2 3 100

8

 

 

РЕШЕНИЕ

рекурсия

 

Анализ алгоритма

Для возведения в степень xn mod m воспользуемся рекурсивной формулой:

xn mod m =

 

Рассмотрим итерационный алгоритм возведения в степень.

 

Любое число n можно представить в двоичной системе:

n = bk 2k + … + b1 21 + b0 20

Например:

13 = 11012 = 8 + 4 + 1

Используя это представление, степень x13 можно переписать как произведение степеней двойки:

x13 = x8 ∙ x4 ∙ x1

Для вычисления степени необходимо умножать только те степени, где бит в двоичном представлении равен 1.

Чтобы собрать любую степень xn, достаточно иметь только степени вида:

x1, x2, x4, x8, x16, …

Алгоритм вычисления xn просматривает биты числа n от младшего к старшему и на каждой итерации:

·        если текущий бит числа n равен 1, умножаем ответ res на текущую степень x;

·        основание x возводим в квадрат;

·        показатель степени n сдвигаем вправо на один бит (делим n на 2).

 

13 = 11012

 

n

бит

степень x

res

13

1

x1

x1

6

0

x2

x1

3

1

x4

x5

1

1

x8

x13

 

Реализация алгоритма – рекурсия

Функция powmod вычисляет значение xn mod m.

 

long long powmod(long long x, long long n, long long m)

{

  if (n == 0) return 1;

  if (n % 2 == 0) return powmod((x * x) % m, n / 2, m);

  return (x * powmod(x, n - 1, m)) % m;

}

 

Основная часть программы. Читаем входные данные.

 

scanf("%lld %lld %lld", &x, &n, &m);

 

Вычисляем значение xn mod m.

 

res = powmod(x, n, m);

 

Выводим ответ.

 

printf("%lld\n", res);

 

Реализация алгоритма – итерация

Функция powmod вычисляет значение xn mod m.

 

long long powmod(long long x, long long n, long long m)

{

  long long res = 1;

  while (n > 0)

  {

    if (n & 1) res = (res * x) % m;

    x = (x * x) % m;

    n >>= 1;

  }

  return res;

}

 

Основная часть программы. Читаем входные данные.

 

scanf("%lld %lld %lld", &x, &n, &m);

 

Вычисляем значение xn mod m.

 

res = powmod(x, n, m);

 

Выводим ответ.

 

printf("%lld\n", res);

 

Java реализация

 

import java.util.*;

 

public class Main

{

  static long PowMod(long x, long n, long m)

  {

    if (n == 0) return 1;

    if (n % 2 == 0) return PowMod((x * x) % m, n / 2, m);

    return (x * PowMod(x, n - 1, m)) % m;

  }

  public static void main(String[] args)

  {

    Scanner con = new Scanner(System.in);

    long x = con.nextLong();

    long n = con.nextLong();

    long m = con.nextLong();

    long res = PowMod(x, n, m);

    System.out.println(res);

    con.close();

  }

}

 

Java реализация – BigInteger

 

import java.util.*;

import java.math.*;

 

public class Main

{

  public static void main(String[] args)

  {

    Scanner con = new Scanner(System.in);     

    BigInteger a = con.nextBigInteger();

    BigInteger b = con.nextBigInteger();

    BigInteger m = con.nextBigInteger();

    System.out.println(a.modPow(b, m));   

    con.close();

  }

}

 

Python реализация – pow

Читаем входные данные.

 

x, n, m = map(int, input().split())

 

Вычисляем и выводим ответ.

 

print(pow(x, n, m))

 

Python реализация – рекурсия

Функция myPow вычисляет значение xn mod m.

 

def myPow(x, n, m):

  if (n == 0): return 1

  if (n % 2 == 0): return myPow((x * x) % m, n / 2, m)

  return (x * myPow(x, n - 1, m)) % m

 

Основная часть программы. Читаем входные данные.

 

x, n, m = map(int, input().split())

 

Вычисляем и выводим ответ.

 

print(myPow(x, n, m))